In networks, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The shortest path is utilized, for example, in provisioning a new demand on the network. Various techniques exist in the art for determining the shortest path in a network. Recent techniques have focused on a Constrained Shortest Path First (CSPF) and related work for Internet Protocol (IP), Layer Two networks such as Ethernet, and Layer One networks (e.g., Synchronous Optical Network (SONET), Synchronous Digital Hierarchy (SDH), Optical Transport Network (OTN), etc.) in which forbidden sub-paths generally do not occur or can be engineered out. For example, one technique is Dijkstra's Algorithm which is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree.
Routing in a wavelength division multiplexing (WDM) agile network requires an algorithm that can find the shortest path while avoiding forbidden sub-paths as some reconfigurable optical add/drop multiplexer (ROADM) sites are non-fully meshed. A non-fully meshed node is a node of a plurality of degrees where some of the degrees lack connectivity therebetween. Furthermore, typically routing requests are for bi-directional paths across an optical network which is inherently unidirectional technology. Lastly, due to the physical construction of a wavelength selective switch (WSS) or other type of photonic cross-connect and how it must be interconnected to create a ROADM, entering in one photonic direction does not result in the same set of paths as entering the same node from a different photonic direction. Conventional solutions to finding a bi-directional path across non-fully meshed networks appear to assume no a priori knowledge of the routing area, and furthermore do not leverage domain specific information (i.e., ROADM behavior) to achieve a fast routing solution. In short, the Dijkstra's Algorithm works for unidirectional connections in a unidirectional photonic network but not for bidirectional connections in a unidirectional photonic network.